package com.wuxuan.priorityQueue;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 优先队列
 * <p>
 * 在 Java 中， java.uti1.PriorityQueue 类是优先队列的一个实现，它基于最小堆实现，即默认情况下，队列
 * 头部的元素是队列中最小的元素。
 */
public class PriorityQueueDemo {

    public static void main(String[] args) {
        //创建优先队列:PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();创建了一个存储 Integer 类型元素的优先队列。
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        //插入元素:使用 offer()方法向队列中插入元素，插入后队列会自动调整以维护最小堆的性质。
        priorityQueue.offer(3);
        priorityQueue.offer(1);
        priorityQueue.offer(2);

        //查看队列头部元素: peek()方法返回队列头部的元素，但不会将其从队列中移除。
        System.out.println(priorityQueue.peek());

        //移除并返回队列头部元素: po11()方法移除并返回队列头部的元素，每次移除后队列会重新调整
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }

    }

    /**
     * 最小K个数
     * <p>
     * 给定一个数组，返回最小K个数
     * 例如:
     * 输入:[4,2,3,5,1]K=2输出:[1,2]// 输出的顺序可以任意
     * <p>
     * 暴力解法
     * -排序:[1,2,3,4,5]
     * Step 1: 0(nlogn)
     * Step 2: O(K)
     * Time: o(nlogn)
     * Space: O(k + logn)
     *
     * @param nums
     * @param k
     * @return 解法一:优先队列
     */
    public int[] getKMinElements(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return null;
        }
        if (k >= nums.length) {
            return nums;
        }

        //使用大顶堆，容量为k
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (a, b) -> b - a);
//        for (int i = 0; i < nums.length; i++) {
//            //遍历数组，把数组每个数放入大顶堆,全都放，效率太低！！！要有判断！！！
//            maxHeap.offer(nums[i]);
//        }
        for (int num : nums) {
            //先放满k个进堆
            if (maxHeap.size() < k) {
                maxHeap.offer(num);
            } else if (num < maxHeap.peek()) {
                //如果已经放满了k个，接下来遍历之后，跟队列中peek即最大值对比，如果比最大值小，则删除最大值(堆顶元素)poll,并将当前值加入队列
                maxHeap.poll();
                maxHeap.offer(num);
            }
        }

        //遍历完数组后，堆中已经拥有最小k个数，此时存入结果数组
        int[] result = new int[k];
        int index = k - 1;
        while (!maxHeap.isEmpty()) {
            result[index--] = maxHeap.poll();
        }

        return result;
    }

    /**
     * 最小K个数
     * <p>
     * 解法二:快速选择
     */
    public int[] getKMinElements2(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return null;
        }
        if (k >= nums.length) {
            return nums;
        }

        //要找k个，即 0， 1， ... , k - 1 , 即左边都快排好后，找到索引为k - 1的位置
        quickSelectK1(nums, 0, nums.length - 1, k - 1);
        //copyOfRange中第三个参数to是不包含的，所以这里传的是k，实际复制范围为索引0到k-1的数
        return Arrays.copyOfRange(nums, 0, k);
    }

    /**
     * 使前k个是前k个小的元素
     * @param nums
     * @param left
     * @param right
     * @param k
     */
        private void quickSelectK1(int[] nums, int left, int right, int k) {
        if (left >= right) {
            return;
        }

        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k) {
            return;
        } else if (pivotIndex < k) {
            quickSelectK1(nums, pivotIndex + 1, right, k);
        } else {
            quickSelectK1(nums, left, pivotIndex - 1, k);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int i = left;
        int j = right - 1;//???
        while (i <= j) {
            if (nums[i] <= nums[right]) {
                i++;
            } else {
                swap(nums, i, j);
                j--;
            }
        }
        swap(nums, i, right);
        return i;
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    /**
     * 这里自个补充了一个 返回第k小的元素方法
     * @param q
     * @param l
     * @param r
     * @param k
     * @return
     */
    private int quickSelectK2(int[] q, int l, int r, int k) {
        if (l >= r) {
            return q[l];
        }
        int x = q[(l + r) / 2];
        int i = l;
        int j = r;
        while (i < j) {
            while (q[i] < x) {
                i++;
            }
            while (q[j] > x) {
                j--;
            }
            if (i < j) {
                swap(q, i, j);
            }

        }
        int sl = j - l + 1;
        if (k <= sl) {
            return quickSelectK2(q, l, j, k);
        } else  {
            return quickSelectK2(q, j + 1, r, k - sl);
        }
    }


}
